// 375. 猜数字大小 II

function getMoneyAmount(n: number): number {
    const cache = new Map<number,Map<number,number>>()
    return get(1,n,cache)
};

function get(start:number,end:number,cache:Map<number,Map<number,number>>):number{
    if(start>=end) return 0
    if(!cache.has(start))cache.set(start,new Map())
    const startMap = cache.get(start)!
    if(startMap.has(end)) return startMap.get(end)!

    let min = Number.MAX_SAFE_INTEGER
    for(let i=start;i<=end;i++){
        const t = Math.max(get(start,i-1,cache),get(i+1,end,cache))+i
        min = Math.min(min,t)
    }
    startMap.set(end,min)
    return min
}

//和扔鸡蛋好像

//! 转换成dp
// dp[i][j] = min for k (max dp[i][k-1],max[k+1][j])+k
// 从对角线向右上方迭代
// dp[i][i] = 0